## Legendre character and the functions QR and NQR
from PyM import *

def legendre(x,F):
    if x==0: return 0
    q = cardinal(F)
    p = characteristic(F)
    if p==2:
        return "legendre: {} is even, so legendre is not defined".format(q)
    u = x**((q-1)//2)
    if u==1: return 1
    else: return -1
    

def QR(F):
    X = Set(F)[1:]
    q = len(X)+1
    if q%2==0: return X
    R = []
    for x in X:
        if x**((q-1)//2)==1: R += [x]
    return R
#
def QNR(F):
    X = Set(F)[1:]
    q = len(X)+1
    NR = []
    if q%2==0: return NR
    for x in X:
        if x**((q-1)//2)!= 1: NR += [x]
    return NR
    
F = Zn(19)

show(QR(F))

show(QNR(F))